package experiment1.closestpoints;

public class ClosestPoints2 extends ClosestPoints{
    @Override
    // 分治法未优化，时间复杂度仍然未O(n^2),但实际运行效果要比暴力求解好一点，（同样都是穷举，分治后穷举比直接穷举应该比直接穷举慢才对，这一点一直没相同）
    public double solve(Point[] points, int l, int r) {
        if (l >= r) {
            return Double.MAX_VALUE;
        }
        int mid = (r + l) / 2;
        double d1 = solve(points, l, mid);
        double d2 = solve(points, mid + 1, r);
        return Math.min(Math.min(d1, d2), crossMinDistance(points, l, mid, r));
    }

    public double crossMinDistance(Point[] points, int l, int mid, int r) {
        double mid_dis = Double.MAX_VALUE;
        for (int i = l; i <= mid; i++) {
            for (int j = mid + 1; j <= r; j++) {
                mid_dis = Math.min(mid_dis,points[i].distance(points[j]));
            }
        }

        return mid_dis;
    }
}
